package leetcode101.complex_datastructure;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @class Code7
 * @description 716. 最大栈
 * 设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。
 *
 * 实现 MaxStack 类：
 *
 * MaxStack() 初始化栈对象
 * void push(int x) 将元素 x 压入栈中。
 * int pop() 移除栈顶元素并返回这个元素。
 * int top() 返回栈顶元素，无需移除。
 * int peekMax() 检索并返回栈中最大元素，无需移除。
 * int popMax() 检索并返回栈中最大元素，并将其移除。如果有多个最大元素，只要移除 最靠近栈顶 的那个。
 *  
 *
 * 示例：
 *
 * 输入
 * ["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
 * [[], [5], [1], [5], [], [], [], [], [], []]
 * 输出
 * [null, null, null, null, 5, 5, 1, 5, 1, 5]
 *
 * 解释
 * MaxStack stk = new MaxStack();
 * stk.push(5);   // [5] - 5 既是栈顶元素，也是最大元素
 * stk.push(1);   // [5, 1] - 栈顶元素是 1，最大元素是 5
 * stk.push(5);   // [5, 1, 5] - 5 既是栈顶元素，也是最大元素
 * stk.top();     // 返回 5，[5, 1, 5] - 栈没有改变
 * stk.popMax();  // 返回 5，[5, 1] - 栈发生改变，栈顶元素不再是最大元素
 * stk.top();     // 返回 1，[5, 1] - 栈没有改变
 * stk.peekMax(); // 返回 5，[5, 1] - 栈没有改变
 * stk.pop();     // 返回 1，[5] - 此操作后，5 既是栈顶元素，也是最大元素
 * stk.top();     // 返回 5，[5] - 栈没有改变
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-06 8:37
 */
public class Code7 {
}
class MaxStack {
    Stack<Integer> stack;
    PriorityQueue<Integer> queue;

    public MaxStack() {
        stack = new Stack<>();
        queue = new PriorityQueue<>(Comparator.reverseOrder());
    }

    public void push(int x) {
        stack.push(x);
        queue.add(x);
    }

    public int pop() {
        int res = stack.pop();
        queue.remove(res);
        return res;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return queue.peek();
    }

    public int popMax() {
        int max = peekMax();
        Stack<Integer> buffer = new Stack<>();
        while (top() != max) {
            buffer.push(pop());
        }
        pop();
        while (!buffer.isEmpty()) {
            push(buffer.pop());
        }
        return max;
    }
}
